// 给定一个二叉树，检测它是否左右对称的

// 思路：递归，不断的比较left和right，在下一轮递归中，需要在left.left和right。right比较，left.right和right.left比较
// 时间复杂度：O(n)，n是二叉树的节点数  
// 空间复杂度：O(n)，递归栈的大小
function isSymmetric(root) {

    function check(left, right) {
        if (!left && !right) {
            return true
        }
        if (!left || !right) {
            return false
        }
        if (left.val !== right.val) {
            return false
        }
        return check(left.left, right.right) && check(left.right, right.left)
    }
    return check(root.left, root.right)
}

// 思路2：遍历队列
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，queue的大小

function isSymmetric2(root) {
    let queue = [root.left, root.right]
    while (queue.length) {
        let leftNode = queue.shift()
        let rightNode = queue.shift()
        if (!leftNode && !rightNode) {
            continue
        }
        if (!leftNode || !rightNode || leftNode.val !== rightNode.val) {
            return false
        }
        queue.push(leftNode.left)
        queue.push(rightNode.right)
        queue.push(leftNode.right)
        queue.push(rightNode.left)
    }
    return true
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: {
            val: 3,
            left: {
                val: 4,
                left: null,
                right: null
            },
            right: null
        },
    },
    right: {
        val: 2,
        left: {
            val: 3,
            left: null,
            right: {
                val: 4,
                left: null,
                right: null
            }
        },
        right: null
    },
};

console.log(isSymmetric(root))
console.log(isSymmetric2(root))